package 树;

public class TrieTree {
	public static class TrieNode{
		public int path; //经过节点node的字符串数量
		public int end; //以节点node结尾的字符串数量
		public TrieNode[] nexts;  //节点node的子节点
		
		public TrieNode() {
			path=0;
			end=0;
			nexts=new TrieNode[26]; //26个字母，所以设置为26
		}
	}
	
	public static class Trie {
		private TrieNode root;
		public Trie() {
			root = new TrieNode();
		}
		public void insert(String word) {
			if (word==null) {
				return;
			}
			char[] chas=word.toCharArray();
			TrieNode node=root;
			int index=0;
			for (int i = 0; i < chas.length; i++) {
				index=chas[i]-'a';
				if (node.nexts[index] == null) { //没有走向node.nexts[index] 的路，新建一个
					node.nexts[index] = new TrieNode();
				}
				node=node.nexts[index];
				node.path++;
			}
			node.end++;
		}
		
		public int search(String word) {
			if (word==null) {
				return 0;
			}
			char[] chas = word.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chas.length; i++) {
				index = chas[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.end;
		}
		
		public void delete(String word) {
			if (search(word)!=0) {
				char[] chas=word.toCharArray();
				TrieNode node=root;
				int index=0;
				for (int i = 0; i < chas.length; i++) {
					index=chas[i]-'a';
					if (--node.nexts[index].path == 0) {
						node.nexts[index] = null;
						return;
					}
					node=node.nexts[index];
				}
				node.end--;
			}
		}
		public int prefixNumber(String pre) {
			if (pre == null) {
				return 0;
			}
			char[] chas = pre.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chas.length; i++) {
				index = chas[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.path;
		}
		
	}
	public static void main(String[] args) {
		Trie trie = new Trie();
		System.out.println(trie.search("zuo"));
		trie.insert("zuo");
		System.out.println(trie.search("zuo"));
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.insert("zuo");
		trie.insert("zuo");
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.delete("zuo");
		System.out.println(trie.search("zuo"));
		trie.insert("zuoa");
		trie.insert("zuoac");
		trie.insert("zuoab");
		trie.insert("zuoad");
		trie.delete("zuoa");
		System.out.println(trie.search("zuoa"));
		System.out.println(trie.prefixNumber("zuo"));

	}
	

}
